package com.sheng.leetcode.year2023.month01.day05;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/01/05
 * <p>
 * 1803. 统计异或值在范围内的数对有多少<p>
 * <p>
 * 给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。<p>
 * 漂亮数对 是一个形如 (i, j) 的数对，其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [1,4,2,7], low = 2, high = 6<p>
 * 输出：6<p>
 * 解释：所有漂亮数对 (i, j) 列出如下：<p>
 * - (0, 1): nums[0] XOR nums[1] = 5<p>
 * - (0, 2): nums[0] XOR nums[2] = 3<p>
 * - (0, 3): nums[0] XOR nums[3] = 6<p>
 * - (1, 2): nums[1] XOR nums[2] = 6<p>
 * - (1, 3): nums[1] XOR nums[3] = 3<p>
 * - (2, 3): nums[2] XOR nums[3] = 5<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [9,8,4,2,1], low = 5, high = 14<p>
 * 输出：8<p>
 * 解释：所有漂亮数对 (i, j) 列出如下：<p>
 * - (0, 2): nums[0] XOR nums[2] = 13<p>
 * - (0, 3): nums[0] XOR nums[3] = 11<p>
 * - (0, 4): nums[0] XOR nums[4] = 8<p>
 * - (1, 2): nums[1] XOR nums[2] = 12<p>
 * - (1, 3): nums[1] XOR nums[3] = 10<p>
 * - (1, 4): nums[1] XOR nums[4] = 9<p>
 * - (2, 3): nums[2] XOR nums[3] = 6<p>
 * - (2, 4): nums[2] XOR nums[4] = 5<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 2 * 10^4<p>
 * 1 <= nums[i] <= 2 * 10^4<p>
 * 1 <= low <= high <= 2 * 10^4<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/count-pairs-with-xor-in-a-range">1803. 统计异或值在范围内的数对有多少</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1803 {

    @Test
    public void test01() {
//        int[] nums = {1, 4, 2, 7};
//        int low = 2, high = 6;
        int[] nums = {9, 8, 4, 2, 1};
        int low = 5, high = 14;
        System.out.println(new Solution().countPairs(nums, low, high));
    }
}

/**
 * 对于这种区间 [low, high] 统计的问题，我们可以考虑将其转换为统计 [0, high] 和 [0, low - 1] 的问题，然后相减即可得到答案。
 * 在这道题中，我们可以统计有多少数对的异或值小于 high+1，然后再统计有多少数对的异或值小于 low，相减的结果就是异或值在区间 [low, high] 之间的数对数量。
 * 另外，对于数组异或计数问题，我们通常可以使用“0-1 字典树”来解决。
 * 字典树的节点定义如下：
 * children[0] 和 children[1] 分别表示当前节点的左右子节点；
 * cnt 表示以当前节点结尾的数的数量。
 * 在字典树中，我们还定义了以下两个函数：
 * 其中一个函数是 insert(x)，表示将数 x 插入到字典树中。该函数将数字 x 按照二进制位从高到低的顺序，插入到“0-1 字典树”中。
 * 如果当前二进制位为 0，则插入到左子节点，否则插入到右子节点。然后将节点的计数值 cnt 加 1。
 * 另一个函数是 search(x, limit)，表示在字典树中查找与 x 异或值小于 limit 的数量。该函数从字典树的根节点 node 开始，遍历 x 的二进制位，从高到低，记当前 x 的二进制位的数为 v。
 * 如果当前 limit 的二进制位为 1，此时我们可以直接将答案加上与 x 的当前二进制位 v 相同的子节点的计数值 cnt，然后将当前节点移动到与 x 的当前二进制位 v 不同的子节点，
 * 即 node = node.children[v ^ 1]。继续遍历下一位。如果当前 limit 的二进制位为 0，此时我们只能将当前节点移动到与 x 的当前二进制位 v 相同的子节点，
 * 即 node = node.children[v]。继续遍历下一位。遍历完 x 的二进制位后，返回答案。
 * 有了以上两个函数，我们就可以解决本题了。
 * 我们遍历数组 nums，对于每个数 x，我们先在字典树中查找与 x 异或值小于 high+1 的数量，然后在字典树中查找与 x 异或值小于 low 的数对数量，将两者的差值加到答案中。
 * 接着将 x 插入到字典树中。继续遍历下一个数 x，直到遍历完数组 nums。最后返回答案即可。
 * <p>
 * 作者：lcbin
 * 链接：<a href="https://leetcode.cn/problems/count-pairs-with-xor-in-a-range/solution/by-lcbin-bmz4/">...</a>
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class Trie {

    /**
     * children[0] 和 children[1] 分别表示当前节点的左右子节点
     */
    private Trie[] children = new Trie[2];

    /**
     * cnt 表示以当前节点结尾的数的数量
     */
    private int cnt;

    /**
     * 将数字 x 按照二进制位从高到低的顺序，插入到“0-1 字典树”中
     *
     * @param x x
     */
    public void insert(int x) {
        // 如果当前二进制位为 0，则插入到左子节点，否则插入到右子节点。然后将节点的计数值 cnt 加 1
        Trie node = this;
        for (int i = 15; i >= 0; --i) {
            int v = (x >> i) & 1;
            if (node.children[v] == null) {
                node.children[v] = new Trie();
            }
            node = node.children[v];
            ++node.cnt;
        }
    }

    /**
     * 在字典树中查找与 x 异或值小于 limit 的数量
     *
     * @param x     x
     * @param limit limit
     * @return 数量
     */
    public int search(int x, int limit) {
        /**
         * 从字典树的根节点 node 开始，遍历 x 的二进制位，从高到低，记当前 x 的二进制位的数为 v。
         * 如果当前 limit 的二进制位为 1，此时我们可以直接将答案加上与 x 的当前二进制位 v 相同的子节点的计数值 cnt，然后将当前节点移动到与 x 的当前二进制位 v 不同的子节点，
         * 即 node = node.children[v ^ 1]。继续遍历下一位。如果当前 limit 的二进制位为 0，此时我们只能将当前节点移动到与 x 的当前二进制位 v 相同的子节点，
         * 即 node = node.children[v]。继续遍历下一位。遍历完 x 的二进制位后，返回答案。
         */
        Trie node = this;
        int ans = 0;
        for (int i = 15; i >= 0 && node != null; --i) {
            int v = (x >> i) & 1;
            if (((limit >> i) & 1) == 1) {
                // 当前 limit 的二进制位为 1，此时我们可以直接将答案加上与 x 的当前二进制位 v 相同的子节点的计数值 cnt，然后将当前节点移动到与 x 的当前二进制位 v 不同的子节点
                if (node.children[v] != null) {
                    ans += node.children[v].cnt;
                }
                node = node.children[v ^ 1];
            } else {
                // 当前 limit 的二进制位为 0，此时我们只能将当前节点移动到与 x 的当前二进制位 v 相同的子节点
                node = node.children[v];
            }
        }
        return ans;
    }
}

class Solution {
    public int countPairs(int[] nums, int low, int high) {
        // 字典树
        Trie trie = new Trie();
        int ans = 0;
        // 循环数组
        for (int x : nums) {
            // 将其转换为统计 [0, high] 和 [0, low - 1] 的问题，然后相减即可得到答案
            ans += trie.search(x, high + 1) - trie.search(x, low);
            trie.insert(x);
        }
        return ans;
    }
}

// 暴力破解，超时
//class Solution {
//    public int countPairs(int[] nums, int low, int high) {
//        /**
//         * 二进制异或：相同为 0，异为 1
//         */
//        int count = 0;
//        int length = nums.length;
//        for (int i = 0; i < length; i++) {
//            for (int j = i + 1; j < length; j++) {
//                if ((nums[i] ^ nums[j]) >= low && (nums[i] ^ nums[j]) <= high) {
//                    count++;
//                }
//            }
//        }
//        return count;
//    }
//}
